We propose some domain-independent techniques for bringing well-foundedpartial-order planners closer to practicality. The first two techniques areaimed at improving search control while keeping overhead costs low. One isbased on a simple adjustment to the default A* heuristic used by UCPOP toselect plans for refinement. The other is based on preferring ``zerocommitment'' (forced) plan refinements whenever possible, and using LIFOprioritization otherwise. A more radical technique is the use of operatorparameter domains to prune search. These domains are initially computed fromthe definitions of the operators and the initial and goal conditions, using apolynomial-time algorithm that propagates sets of constants through theoperator graph, starting in the initial conditions. During planning, parameterdomains can be used to prune nonviable operator instances and to removespurious clobbering threats. In experiments based on modifications of UCPOP,our improved plan and goal selection strategies gave speedups by factorsranging from 5 to more than 1000 for a variety of problems that are nontrivialfor the unmodified version. Crucially, the hardest problems gave the greatestimprovements. The pruning technique based on parameter domains often gavespeedups by an order of magnitude or more for difficult problems, both with thedefault UCPOP search strategy and with our improved strategy. The Lisp code forour techniques and for the test problems is provided in on-line appendices.
展开▼
